module UTuringMachine
  class Configuration < Struct.new(:state, :tape)
  end

  class Tape < Struct.new(:left, :down, :right, :blank)
      def to_s    = "#<Tape #{left.join}(#{down})#{right.join}>"
      def inspect = "#<Tape #{left.join}(#{down})#{right.join}>"

      def none_move  = self
      def right_move = Tape.new(left + [down], right.first || blank, right.drop(1), blank)
      def left_move  = Tape.new(left[0..-2], left.last || blank, [down] + right, blank)

      def write(character) = Tape.new(left, character, right, blank)
  end

  class Rule < Struct.new(:current_state, :character, :next_state, :write_character, :direction)
      def self.[](current_state, character, next_state, write_character, direction)
          Rule.new(current_state, character, next_state, write_character, direction)
      end
      def apply_to?(configuration)
          @current_state == configuration.state && @character == configuration.tape.down
      end
      def follow(configuration)
          Configuration.new(next_state, next_tape(configuration))
      end
      def next_tape(configuration)
          written_tape = configuration.tape.write(write_character)
          case direction
          when :l
              written_tape.left_move
          when :r
              written_tape.right_move
          when :n
              wirtten_tape.none_move
          end
      end
  end

  class Rulesbook < Struct.new(:rules)
      def next_configuration(configuration)
          rules_for(configuration).follow(configuration)
      end
      def rules_for(configuration)
          rules.detect {|rule| rule.apply_to?(configuration)}
      end
      def apply_to?(configuration)
          !rules_for(configuration).nil?
      end
  end

  class DTM < Struct.new(:current_configuration, :accept_states, :rulesbook)
      def accepting?
          accept_states.include?(current_configuration.state)
      end
      def step
          current_configuration = rulesbook.next_configuration(current_configuration)
      end
      def run
          step until accepting?
      end
      def stuck?
          !rulesbook.apply_to?(current_configuration) && !accepting?
      end
      def run
          step until accepting? || stuck?
      end
  end
end
